package BFS;

import java.util.*;

/**
 * 在getNeighbors那个函数里，一开始我是把code当作一个char[]类型的数组当作形参在传
 * 但是这样子有个坏处，随着我onePlus和oneSubtract函数运行，code会被修改的一塌糊涂，因为code为当作指针传来传去
 * 每次修改都会被保留
 * 所以我们选择把code当作String类型的参数
 * String类型的参数永远不会变
 */

public class Solution752 {

    public int openLock(String[] deadends, String target) {
        //感觉BFS题目最难的就是设计如何获取邻居这一个部分
        //如何获取邻居这一部分设计好了，接下来就是默写BFS的框架了
        HashSet<String> visited = new HashSet<>();
        HashSet<String> deadend = new HashSet<>();
        //起始位置
        String start = "0000";
        int step = 0;

        //使用hashSet来记录死亡之步，判定时间能快一点
        for (int i = 0; i < deadends.length; i++) {
            deadend.add(deadends[i]);
        }

        Queue<String> queue = new LinkedList<>();
        if (!deadend.contains(start)){
            queue.offer(start);
            visited.add(start);
        }


        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)){
                    return step;
                }
                for (String neighbor : getNeighbors(cur)) {

                    if (deadend.contains(neighbor)){
                        continue;
                    }
                    if (!visited.contains(neighbor)){
                        queue.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }

            step++;
        }

        return -1;
    }

    public List<String> getNeighbors(String code){

        List<String> neighbors = new ArrayList<>();

        for (int i = 0; i < code.length(); i++) {
            //将code[i]加一,感觉得设计个子函数
            //因为我们要设计一个临时变量来让集合接收邻居
            //设计个子函数方便临时变量接收对象
            String onePlusNeighbor = onePlus(code,i);
            //将这个邻居加入到集合中
            neighbors.add(onePlusNeighbor);
            //将code[i]减一
            String oneSubtractNeighbor = oneSubtract(code,i);
            neighbors.add(oneSubtractNeighbor);

        }

        return neighbors;
    }

    //用来将code[i]加上一个1
    public String onePlus(String code,int i){
        char [] codeModify = code.toCharArray();
        int digit = codeModify[i]-'0';
        int newDigit = (digit+1) % 10;
        codeModify[i] =(char)( newDigit+'0');

        return new String(codeModify);
    }

    public String oneSubtract(String code,int i){
        char [] codeModify = code.toCharArray();
        int digit = codeModify[i]-'0';
        int newDigit = (digit - 1 + 10) % 10;
        codeModify[i] = (char) (newDigit + '0');

        return new String(codeModify);
    }

    public static void main(String[] args) {
        String[] deadends = new String[]{"0201","0101","0102","1212","2002"};
        String target = "0202";

        Solution752 solution752 = new Solution752();
        int i = solution752.openLock(deadends, target);
        System.out.println("i = " + i);
        /*String code = "0000";
        List<String> neighbors = solution752.getNeighbors(code);
        for (String neighbor : neighbors) {
            System.out.println("neighbor = " + neighbor);
        }*/
    }

}
